package org.zdw.data.structure.sort;

import org.zdw.data.structure.util.ExecutionCounter;

/**
 * 直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
 *设数组为a[0…n-1]。
 *1）初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1
 *2）将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。
 *3）i++并重复第二步直到i==n-1。排序完成。
 */
public class InsertSort implements Sort{

    public void sort(int[] array){
        int temp = 0;
        for (int i = 1 ; i < array.length ; i++){
            int j = i-1;
            temp = array[i];
            for (;j >= 0 && temp < array[j] ; j--){
                array[j+1] = array[j];
            }
            ExecutionCounter.getInstance().increase();
            array[j+1] = temp;
        }
    }

    public void improvedSort(int[] array) {
        int temp = 0 ;
        for(int i = 1; i < array.length ; i++){

        }
    }
}
